//https://leetcode.cn/problems/minimum-fuel-cost-to-report-to-the-capital/submissions/486849890/?envType=daily-question&envId=2023-12-05


class Solution {
public:
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        int n=roads.size()+1;//n条路
        vector<vector<int>> e(n+1);
        for(auto& v:roads)
        {
            e[v[0]].push_back(v[1]);
            e[v[1]].push_back(v[0]);
        }
        long long ans=0;
        function<int(int,int)> dfs=[&](int begin,int end)->int{
            int ret=1;
            for(int i=0;i<e[begin].size();++i)
            {
                if(e[begin][i]==end) continue;
                ret+=dfs(e[begin][i],begin);
            }
            if(begin!= 0) ans+=(ret+seats-1)/seats;
            return ret;
        };
        dfs(0,-1);
        return ans;
    }
};